1. Field of the Invention
The present invention is directed to computer systems. More particularly, it is directed to coordination mechanisms for concurrent programming in computer systems.
2. Description of the Related Art
In the field of computer systems, considerable effort has been expended on developing techniques to support concurrent access to shared resources. Mutual exclusion locks and monitors represent two traditional concurrent programming synchronization mechanisms. Locks and monitors protect shared resources by separating access to them in time; for example, in one implementation, as long as a given thread of execution retains a lock on an object or resource, no other thread of execution may modify the object, and any other thread attempting to modify the object may be blocked from further execution until the lock is released.
However, traditional locking techniques are known to suffer from several limitations. Coarse-grained locks, which protect relatively large amounts of data, often do not scale. For example, threads of execution on a multiprocessor system may block each other even when they do not actually require concurrent access to the same addresses. Fine-grained locks may resolve some of these contention issues, but in traditional locking techniques, this may be achieved only at the cost of added programming complexity and the increased likelihood of problems such as deadlocks. Locking schemes may also lead to an increased vulnerability to thread failures and delays—e.g., a thread that is preempted or does expensive input/output operations while holding a lock may obstruct other threads for relatively long periods, thereby potentially reducing the overall throughput of the system.
The transactional-memory programming paradigm has been gaining momentum as an approach of choice for replacing locks in concurrent programming. In transactional-memory programming, single-threaded sequences of concurrent operations may be combined into non-blocking atomic transactions, thus making parts of the code appear to be sequential without requiring locks. Executing threads indicate transaction boundaries, e.g., by specifying when a transaction starts and when it ends, but may not have to acquire locks on any objects. Transactional-memory programming techniques may allow transactions that do not overlap in data accesses to run uninterrupted in parallel; transactions that do overlap may be aborted and retried.
Transactional-memory may, at least in principle, be implemented using special hardware support (e.g., by enhancing existing hardware memory management mechanisms to support atomic programmer-specified transactions) and/or using software-only techniques (e.g., using extensions to conventional programming languages such as Java™). Support for hardware transactional-memory (HTM) has not yet been implemented extensively, however, at least in commercially available systems; as a result, current implementations of transactional-memory are largely software based. Unfortunately, conventionally known software transactional-memory (STM) implementations are fairly inefficient, in part because of the need to provide a mechanism to allow one transaction to roll back another. In addition, most HTM implementations developed within the near term are expected to place relatively severe limits on allowed transaction size (i.e., on the number of operations that may be performed within a given transaction) supported entirely in hardware.